Internet Info 1994 March/Internet Info CD-ROM (Walnut Creek) (March 1994).iso/inet/ien/ien-183

Text File | 1988-12-01 | 92KB | 3,306 lines

IEN-183






















                       Logical Addressing

                  Bolt Beranek and Newman Inc.

                          Eric C. Rosen

                            May 1981




























IEN-183                              Bolt Beranek and Newman Inc.
                                                    Eric C. Rosen



                        Table of Contents




1   Introduction.......................................... 1
2   Translating Logical to Physical Addresses............. 7
2.1   Translation Locus................................... 7
2.2   Translation Methodology............................ 10
3   Organizing the Translation Tables.................... 17
4   Initializing the Translation Tables.................. 23
5   Updating the Translation Tables...................... 30
6   Operational and Implementation Considerations........ 49
7   Network Access Protocol Implications................. 53



































                               -i-


IEN-183                              Bolt Beranek and Newman Inc.
                                                    Eric C. Rosen



1  Introduction


        This paper is a slightly modified extract from BBN Report

No.  4473,  "ARPANET Routing Algorithm Improvement, Volume 1," by

Rosen, et al.  It proposes  a  scheme  for  implementing  logical

addressing  in  the  ARPANET.  However, the issues dealt with are

quite similar to the issues raised by the problem of implementing

logical  addressing in the Catenet (several IENs are currently in

preparation in which  we  argued  for  this  assertion  at  great

length.)   It is hoped, therefore, that the discussion will be of

interest to internet workers as well.


        In the current ARPANET, in order for a user  to  transmit

data  to  a particular host, he must know the PHYSICAL ADDRESS of

the host.  That is, he must know which node the host is connected

to,  and  he must know which port on that node is used to connect

that host.  Furthermore, this is the ONLY means  a  user  has  of

identifying  a host.  In many respects, the physical address of a

host computer can be compared to  a  person's  telephone  number.

The  problems  inherent  to  physical  addressing  in  a computer

network are similar to those  we  would  experience  in  ordinary

interpersonal  communication  if a person's telephone number were

the only means we had of identifying him.  Dialing  a  particular

telephone  number allows us to establish a communications channel

to a particular location.  This works well as long as the  person



                               -1-


IEN-183                              Bolt Beranek and Newman Inc.
                                                    Eric C. Rosen



with  whom  we  wish  to  communicate  remains at that particular

location.  When the person  changes  his  location,  though,  the

phone  number becomes virtually useless, and the physical address

of a host computer becomes  equally  useless  if  the  computer's

location   within   the  network  changes.   In  the  context  of

interpersonal communication, this gives rise to the calling of  a

"wrong  number".  In the context of computer networking, this can

give rise to the more serious phenomenon of mis-delivery of data.

Furthermore,  when  a computer changes location within a network,

it is quite difficult to carry out  a  procedure  which  reliably

informs  all  users  of  its  new  physical  address.   There are

difficulties in identifying all users, difficulties in contacting

them  once  they are identified, difficulties in making sure that

the information receives  the  proper  level  of  attention  once

contact  is  made, and if all these difficulties are resolved, it

is still difficult to make  the  necessary  changes  to  computer

software  so  that  the new physical address is actually put into

use.


        There  is  another  sort  of  problem  would   occur   in

interpersonal  communication  if  our only means of identifying a

person were by his phone number.  It is very common  for  several

people  to share a phone number.  If we identified people only by

phone numbers, we could not distinguish among several  people  at




                               -2-


IEN-183                              Bolt Beranek and Newman Inc.
                                                    Eric C. Rosen



the same location.  This problem arises in computer networking if

several computers share the  same  port.   There  are,  in  fact,

several  reasons  why  it  may  be  desirable  to  allow  several

computers to share the same port.  One reson is simply  the  need

to  get  by  with a less than optimal amount of equipment, either

due to economics or to shortage.  If some administration has  two

computers,  each of which needs to be on the network only part of

the day, but which do not need to be on the network at  the  same

time,  sharing  a  single  port  may  be  the best solution.  The

increasing cost-effectiveness of such devices as  port  expanders

and  local  networks  may also make it more and more desirable to

have several computers sharing the same port.  A related  problem

arises  if  one thinks of a network of computers as consisting of

"logical hosts," rather than physical hosts.  Whereas a  physical

host  would  be  a  particular  piece of hardware, a logical host

would be the instantiation of  a  particular  function.   Thus  a

physical  host  which supported (for example) time-sharing during

the day and batch processing at night could be  regarded  as  two

logical  hosts  which share the port on a time-division basis.  A

related application is the situation in which  the  functionality

of  two  (small)  physical  hosts  is  combined into one (larger)

physical host, which then can be thought of as consisting of  two

logical  hosts.   It could be very useful to have the flexibility

to move logical hosts freely around the network, perhaps changing



                               -3-


IEN-183                              Bolt Beranek and Newman Inc.
                                                    Eric C. Rosen



the correspondence between particular logical and physical hosts,

without having to inform all users of the new physical addresses.


        Of  course,  the  reasons  these  problems  in   computer

networking  are  more  serious  than  the  analogous  problems in

interpersonal communication is that telephone numbers are not the

only,  or  even  the  primary, means we have of identifying other

people.  We can identify other people by NAME, and  this  greatly

facilitates  our ability to get in touch with people even as they

change location.  It also enables us to specify the individual we

wish  to  talk  to, in the situation where several people share a

telephone.  Similar advantages would accrue if we could  identify

computers  by  name rather than by physical address.  In order to

get our data to the appropriate computer,  its  physical  address

would  still  have to be determined.  But the user should be able

to tell the network the name of the appropriate computer (perhaps

a  logical  rather  than  a  physical  host), and let the network

itself map the name to  its  physical  address.   For  speed  and

reliability,   the   mapping   function  should  be  accomplished

automatically (i.e., by software) with  minimal  need  for  human

intervention.   Schemes  to  accomplish this are known as LOGICAL

ADDRESSING schemes,  and  the  name  of  a  computer  is  usually

referred  to  as  its  "logical address" (though in fact, logical

addresses are not addresses at all, since they, like  names,  are




                               -4-


IEN-183                              Bolt Beranek and Newman Inc.
                                                    Eric C. Rosen



independent of location).


        A  good  logical  addressing  scheme  should  allow  more

flexibility  than may be already apparent.  We have spoken of the

need to be able  to  identify  a  computer  in  a  way  which  is

independent  of  location,  and  of  the  need  to be able to map

several distinct names onto a single physical address.  There  is

also a need to be able to map a single name onto several physical

addresses.   To  carry  out  the   analogy   with   interpersonal

communication,  this  would correspond to the case where a single

person has several  telephones,  with  different  phone  numbers,

possibly  at  different  locations.  This adds reliability to the

communications process, since if the person cannot be reached  at

one  phone  number,  perhaps he can be reached at another.  If he

can be reached at each of the numbers, he now can handle  several

conversations  simultaneously, i.e., he has increased throughput.

In computer networking, this sort  of  application  is  known  as

"multi-homing."  In  multi-homing,  a single computer connects to

the  network  through  several   ports,   usually   (though   not

necessarily) at several different network nodes.  This allows the

computer to remain on the network even though one of  its  access

lines,   ports,   or   home   nodes   fails,  thereby  increasing

reliability.  In  the  case  where  it  is  more  economical  (or

otherwise  more  practical)  to  obtain  several low-speed access




                               -5-


IEN-183                              Bolt Beranek and Newman Inc.
                                                    Eric C. Rosen



lines than to obtain a single high speed line,  multi-homing  can

also  allow  a given host computer to obtain higher throughput at

less cost.


        Another sort of application which requires a single  name

to  map  into  several  physical  addresses  can be compared to a

business which has several branch offices, each with a  different

phone number, but whose customers do not care which branch office

they reach.  This can be useful in certain sorts of  internetting

applications.   Suppose,  for example, that an ARPANET user wants

to send a packet to SATNET, but that there  are  several  equally

good gateways between the two networks.  It may be convenient for

the user to simply specify a name  like  "Gateway-to-SATNET"  and

let  the  network  choose  which  of  the several gateways (i.e.,

physical  addresses)  to  use.   A  related  sort   of   possible

application  has  to  do with distributed processing and resource

sharing.  If some particular resource  is  available  at  any  of

several  locations  around  the  network,  it may be desirable to

allow the user to specify the resource by  name,  and  allow  the

network  to  map  that name onto some particular physical address

according to criteria that the user need not be aware of.   (Such

a  service  was  formerly offered by the ARPANET TIPs.  By typing

@N, a user would be connected to a  "Resource-Sharing  Executive"

on  one  of  several  network  TENEX systems.  The user, however,




                               -6-


IEN-183                              Bolt Beranek and Newman Inc.
                                                    Eric C. Rosen



would have no way of knowing which system he was actually on.)




2  Translating Logical to Physical Addresses


2.1  Translation Locus


        It should be obvious that any implementation  of  logical

addressing  would  require  the network to maintain a translation

table.  The user would specify a logical address, and the network

would  use  this logical address as an index into the translation

table in order  to  obtain  the  physical  address  (or  list  of

physical  addresses)  to which it corresponds.  The network would

use the physical address internally to determine the  routing  of

user  messages.   The  need to maintain a translation table gives

rise to a multitude of design issues.  The  first  question  that

needs  to  be  answered is, where should the translation table be

located?   Should  every  node  maintain  a  copy  of  the  whole

translation  table,  or  should there be just a few copies of the

table scattered around the network in  strategic  locations?   If

there  are  only  a few copies scattered around the network, then

nodes which do not contain the tables would  have  to  query  the

nodes that do in order to perform the translation function.  This

is less efficient (both in terms of overhead and  response  time)

than   placing  the  table  in  every  node.   Considerations  of




                               -7-


IEN-183                              Bolt Beranek and Newman Inc.
                                                    Eric C. Rosen



reliability and survivability also favor  placing  the  table  in

every node.  This eliminates the possibility of finding that, due

to network partition, all copies of  the  translation  table  are

inaccessible.   It eliminates the need to have some nodes serving

as hot or cold standby for the nodes which do  have  the  tables.

This  is  an  important  advantage, since the protocols needed to

implement "standby" tend to  be  slow  and  cumbersome,  or  else

unreliable.   Furthermore, if all nodes maintain identical copies

of the translation table, there is no  need  to  go  through  any

special  initialization  procedure  for creating the table when a

node first comes up.  Typically, a node which is just  coming  up

has  been reloaded from a neighboring node.  If all nodes have an

identical copy of the table, a node coming up can simply have its

table  reloaded  from its neighbor, i.e., can copy its neighbor's

table.  (Under certain unusual conditions this may give rise to a

race  condition, but as we shall see later, it is a race that can

be easily remedied and one that will  not  have  any  bad  effect

other than to slow the reload process.)


        There is, however, a possible disadvantage to having  the

tables  in  every  node.   That is simply the need to have enough

memory in every node to hold the  table.   In  certain  networks,

particularly  commercial ones, the network nodes may be of widely

varying sizes and capabilities, and the smaller  nodes  just  may




                               -8-


IEN-183                              Bolt Beranek and Newman Inc.
                                                    Eric C. Rosen



not  be  able  to  hold  the  complete  translation  table.  Such

networks  would  necessarily  have   a   hierarchical   structure

(probably  with  some  form  of hierarchical routing), and a node

would not be able to hold a translation table unless it  were  at

or above a certain level in the hierarchy.


     Strictly speaking, only those nodes which will ever need  to

translate  a  logical  address to a physical address will need to

have a copy of the translation table.  Whether that is all  nodes

or  only  a  subset  of  the  nodes  depends  on  the translation

methodology that we adopt.  We have a  choice  between  requiring

translation  to  be done only at the source node, or requiring it

to be done also at tandem nodes.  In the former  case,  when  the

user  presents  some  data  to  the  network  and  specifies  its

destination with a logical address, the source node looks in  the

translation table, gets the physical address, places the physical

address in the packet header, and sends the packet  on  its  way.

Tandem  nodes  do  not look at the destination logical address at

all, but only at the physical address.  In the other  case,  each

tandem   node   looks  at  the  logical  address,  does  its  own

translation to physical address, and routes the  packet  on  that

basis.   The  packet  header  would  not even have to contain the

physical address.  If we do source  translation  only,  the  only

nodes  which  need  to  contain translation tables are those that




                               -9-


IEN-183                              Bolt Beranek and Newman Inc.
                                                    Eric C. Rosen



connect to hosts which use logical addressing.   If  these  nodes

are  only  a  subset of all the nodes, then it may be feasible to

configure  these  nodes  with  more  memory  than   the   others.

Therefore,  we  must  look  at  the advantages of source node vs.

tandem node translation.




2.2  Translation Methodology


        Clearly, in the case where a logical address  maps  to  a

unique  physical  address, source node translation is superior to

tandem node translation.  As long as there is only  one  possible

physical address for that logical address, all nodes will produce

exactly  the  same  mapping.   There  is  thus  no  advantage  to

performing  the  mapping several times, and the scheme which does

it only once is more efficient.  There is, however, one exception

to  this.   When  the  translation  tables need to be updated, we

cannot expect all copies to  be  updated  simultaneously.   There

will  necessarily  be some short interval of time when not all of

the copies of the table around the  network  are  identical,  and

during this interval, tandem node translation may yield different

results than source  node  translation.   It  will  certainly  be

necessary to design some mechanism to deal with this problem, and

we shall propose one shortly for the ARPANET environment.  Tandem

node  translation,  however,  is  not  the right solution to this



                              -10-


IEN-183                              Bolt Beranek and Newman Inc.
                                                    Eric C. Rosen



problem.  During the transient period, some copies of  the  table

will be right (up to date) and some wrong (out of date).  But the

copies at the tandem nodes will be no more  likely  to  be  right

than  the  copy  at  the  source node, so tandem node translation

would be as likely to amplify the problem as to reduce  it.   The

solution to this problem lies elsewhere.


        In the case where  a  logical  address  maps  to  several

physical  addresses (multi-homing), tandem node translation might

well  give  different  results  than  source  node   translation.

However,  we  must  now  distinguish  between virtual circuit and

datagram  traffic.   If  virtual  circuit  traffic  is  logically

addressed,  all translation must be performed at the source node.

In  fact,  the  translation  must  be  performed  only  once,  at

connection  set-up time.  This is the only way to ensure that all

traffic on a given circuit is sent to the same physical  address,

which  in  turn  is  the  only  way to provide the sequencing and

duplicate detection that is the RAISON D'ETRE of virtual  circuit

traffic.    (Additional   issues  having  to  do  with  logically

addressed virtual circuit traffic will be discussed later.)  Thus

the only possible advantage of tandem node translation would have

to do with datagram traffic which is destined  to  a  multi-homed

logical  address.  To understand the differences, though, between

source node and tandem node translation, we  must  first  discuss




                              -11-


IEN-183                              Bolt Beranek and Newman Inc.
                                                    Eric C. Rosen



the  criteria  which a node uses to pick one physical address out

of the several that are available.  Even though a host is  multi-

homed,  any  particular  packet  for it can go to only one of its

physical addresses; some criterion for choosing the proper one in

each   particular  case  must  therefore  be  available.  Several

possible criteria come readily to mind:


        a)   When   there   are   several   physical    addresses

corresponding  to a given logical address, it may be desirable to

send packets to the physical address  which  is  closest  to  the

source  node, according to some metric of distance.  For example,

if we are interested in minimizing delay, we may want  to  choose

the physical address to which the delay from the source is least.

If SPF routing is used, this information  is  readily  available.

If  we  are interested in minimizing the use of network resources

by a particular packet  (i.e.,  in  maximizing  throughput  while

still  using  only  a  single  path),  we  may want to choose the

physical address which is the  least  number  of  hops  from  the

source.   (For  these  purposes, ties can be broken arbitrarily.)

Again, this information can be made readily available by the  SPF

routing  algorithm (although it is not readily available from the

ARPANET's particular implementation of that  algorithm,  since  a

table  of  hop-counts is not saved).  If either of these criteria

is used, tandem node  translation  can  result  in  better  route




                              -12-


IEN-183                              Bolt Beranek and Newman Inc.
                                                    Eric C. Rosen



selection for the logically addressed datagram.  If delay changes

or topology changes take place while a packet is in  transit,  it

may  happen  that  the  "closest" physical address to some tandem

node is different from the physical address that was  closest  to

the source node when the packet first entered the network.  It is

easy to prove that, if SPF routing is used, this cannot result in

looping,  except as a transient phenomenon while a routing update

is traversing the network.  That is no  particular  disadvantage,

since  a  packet may be subject to that sort of transient looping

even when its  destination  physical  address  does  not  change.

However,  it  is  not clear that tandem node translation provides

much of an advantage  either,  especially  when  one  takes  into

account  the  additional  overhead of doing the re-translation at

each  tandem  node.   Doing  translation  at  tandem  nodes  will

necessarily  increase  the  nodal  delay  and  decrease the nodal

throughput.  These negative effects  may  outweigh  the  positive

effects  of  improved  route  selection for those relatively rare

cases in which delay or topology changes  significantly  while  a

packet  is  in  transit.   We  must  remember  that although real

improvements in route selection would only  occur  rarely  (since

delay and topology changes are very infrequent when compared with

average network transit times), re-translation would have  to  be

done  for EVERY logically addressed datagram.  Unfortunately, all

these effects are extremely difficult to quantify with any degree



                              -13-


IEN-183                              Bolt Beranek and Newman Inc.
                                                    Eric C. Rosen



of  confidence.   Our  (somewhat  intuitive)  conclusion is that,

under the selection criterion of choosing  the  closest  physical

address,   tandem   node  translation  offers  at  best  a  small

improvement over source node translation, and at worst  a  severe

degradation.


        b) It is possible that some multi-homed hosts  will  want

to  establish an inherent ordering to their ports.  That is, they

may prefer to receive all their traffic on port  A,  unless  that

port  is inaccessible to the source of the traffic, in which case

they prefer to receive all traffic on port B, unless that port is

inaccessible  to  the  source  of the traffic, in which case they

prefer to receive all traffic on  port  C,  etc.   This  sort  of

strategy  may  be appropriate if certain of the host access lines

are charged according to a volume-based tariff, while others  are

not.   It  may also be appropriate if certain of the access lines

can be used more efficiently (i.e., can  be  serviced  with  less

host  CPU  bandwidth)  than  others.  (An example might be a host

which can access the ARPANET through an 1822 line and a VDH line.

It  might  be  desirable to avoid the VDH line, unless absolutely

necessary, since VDH lines tend to be used less efficiently.)  In

either case, the idea would be to reduce cost by favoring certain

ports over others, using  the  more  expensive  ports  only  when

needed  for purposes of reliability or availability.  Thus we may




                              -14-


IEN-183                              Bolt Beranek and Newman Inc.
                                                    Eric C. Rosen



want  the  logical  addressing  scheme  to  support  an  inherent

ordering among the several physical addresses which correspond to

a given logical address.  With this scheme, there is no advantage

to  doing  tandem  node  translation.   There  will  be  only one

ordering for the set of physical  addresses  corresponding  to  a

logical  address,  so  tandem  nodes  should always pick the same

physical address as the source node  picked,  and  re-translation

would  simply  be  a  waste  of  resources.   There  are only two

exceptions to this.  The  first  exception  would  arise  in  the

situation   where   a   particular   physical   address   becomes

inaccessible as a packet routed to that address is traversing the

network.   However, since this can happen no matter what criteria

are used for choosing among the physical addresses, we put it off

for later consideration.  The second exception would arise if the

translation tables were  being  updated  while  a  packet  is  in

transit.   Clearly, some procedure to deal with this case must be

devised, since the update which is taking  place  may  invalidate

the  translation  which  was  done  at  the  source.  Tandem node

translation is not the proper solution, however, since  there  is

in  general no reason to believe that the tandem node is more up-

to-date than the source node.  We will return to this issue  when

we discuss the table updating procedures.


        c) Certain multi-homed hosts may have  a  preference  for




                              -15-


IEN-183                              Bolt Beranek and Newman Inc.
                                                    Eric C. Rosen



receiving certain kinds of traffic over particular ports.  Thus a

dual-homed host may consider one of its ports more  suitable  for

receiving  batch traffic, and another more suitable for receiving

interactive traffic (perhaps the first port offers a higher speed

but  a  longer  delay  than  the second).  However, if one of the

ports is inaccessible from a particular source  node,  that  node

would send all its traffic (both kinds) to the port which remains

accessible.  With this criterion, we see once again  that  tandem

node translation offers no benefits, since, barring the case of a

port becoming inaccessible while a  packet  is  in  transit,  all

tandem nodes would select the same physical address as the source

node.


        d) Some multi-homed hosts may wish to try to  keep  their

several access lines as equally loaded as possible.  One possible

way to do this would be to establish an inherent ordering to  the

ports  (as  in  b, above), but to make the ordering different for

different source nodes (or hosts).  Clearly, this scheme requires

source node translation; tandem node translation would only serve

to defeat it.  Another possible way to achieve some sort of  load

leveling  would  be  for  each source node to send traffic to the

various physical addresses on a round-robin basis.  This would be

a  very crude form of control, but might work reasonably well for

particular traffic patterns.  This scheme  also  requires  source




                              -16-


IEN-183                              Bolt Beranek and Newman Inc.
                                                    Eric C. Rosen



node   translation.   In  fact,  tandem  node  translation  could

actually cause packets to loop endlessly.


        We see then that none of the suggested selection criteria

give  any  very  large  advantage to tandem node translation, and

some of the criteria are actually in conflict with re-translation

at  tandem nodes.  Thus it is not necessary for all notes to hold

the translation tables; only those nodes connected to hosts which

use  logical  addressing  need hold the tables.  Of course, it is

still possible that the tables will be too large to  be  held  in

any  one  node,  in  which  case we would have to use distributed

database techniques to split the tables among several nodes.   We

will not consider that further here, but we will consider it in a

future IEN.




3  Organizing the Translation Tables


        Another issue having to do with the translation tables is

the  way  in which the tables should be organized.  Clearly we do

not want the  entries  in  the  table  to  be  in  random  order,

necessitating  a  lengthy  linear  search each time a translation

must be done.  Basically, there are two possible  ways  to  order

the  table.   We  can sort the table by logical address, and do a

binary search of the table whenever we need to do  a  logical-to-




                              -17-


IEN-183                              Bolt Beranek and Newman Inc.
                                                    Eric C. Rosen



physical address translation.  This is a rather efficient form of

searching, but it causes inefficiencies when table  entries  have

to be inserted or deleted, since that would require a potentially

time-consuming expansion or compression of the table.  There are,

however,    ways   of   reducing   the   overhead   involved   in

insertions/deletions.  Deletions could be made "logically", i.e.,

by  marking  an entry deleted, rather than physically compressing

the table.  New entries could be inserted into an overflow  area,

which  itself  would  be  searched linearly whenever a particular

logical address could not be found in  the  main  table.   Actual

compression/expansion  of  the main table would be done only when

the overflow area filled.   Note,  however,  that  this  sort  of

strategy  would  necessarily complicate the search algorithm, and

this might  actually  do  more  harm  than  good,  especially  if

insertions  and  deletions  are rare events.  We shall see later,

when  we  discuss  the  conditions  under  which  insertions  and

deletions  are  required,  that these are indeed rare events.  We

conclude  tentatively  that,  if  a  sorted  table  with   binary

searching  is  used,  the use of an overflow area is probably not

necessary.


        The other possibility for organizing the table is to  use

hashing.   A  good  hashing  algorithm (i.e., one which minimizes

collisions) provides very efficient insertions and very efficient




                              -18-


IEN-183                              Bolt Beranek and Newman Inc.
                                                    Eric C. Rosen



searches.   Deletions  are  not quite so efficient, but are still

more efficient, in general, than the table  compression  required

if  binary  searching  is  used.   However,  hashing  has certain

inherent problems which may make it less  suitable.   Choosing  a

hashing   algorithm   which  both  minimizes  collisions  and  is

computationally efficient is not a simple matter.   One  must  be

sure  that  the time needed to perform the hashing is really less

than the average time needed to find an entry in a  sorted  table

by  means of binary searching; otherwise, the efficiency is lost.

Furthermore, the number of collisions generated by  a  particular

hashing  algorithm  will  depend  on exactly which set of logical

addresses are in use.  The set of logical addresses in use during

a network's lifetime will be a slowly changing set, and a hashing

algorithm  which  is  excellent  at  one  time  may   give   poor

performance  at  another.  Hashing algorithms are also subject to

undetected programming bugs in  a  way  in  which  binary  search

algorithms  are  not.   A  bug  which  is inserted into a hashing

algorithm, which, for example, causes all entries  to  hash  into

the same bucket, might go undetected for years, although it would

cause a  significant  performance  degradation  by  reducing  the

efficiency  of the hashing technique to that of linear searching.

A bug in the binary search  algorithm,  however,  would  be  more

likely to come to someone's attention.  Its probable result would

not be performance  degradation,  but  rather,  failure  to  find



                              -19-


IEN-183                              Bolt Beranek and Newman Inc.
                                                    Eric C. Rosen



certain  entries.   This would cause inability to deliver traffic

to certain logical addresses, and this would  certainly  come  to

the  users'  attention  very  quickly.  These qualitative reasons

would seem to indicate that binary  searching  is  preferable  to

hashing.   It  would  also  be  useful  to  do  some quantitative

analysis; that may be done at a later stage of our research.


        Someone may wonder why we  have  not  considered  a  much

simpler  method  of  organizing  the  tables.  Logical addresses,

after all, are just numbers (or at  least  are  representable  as

numbers).   If  the  set of logical addresses in use at any given

time is a contiguous set of numbers, then the  addresses  can  be

used  as  indexes directly into a translation table, with no need

either for hashing or for sorting.  The problem, of course,  lies

in  the  requirement  that  the  set  of logical addresses form a

contiguous  set  of  numbers.    Assigning   numbers   to   hosts

contiguously  may not be a problem in itself, but it does cause a

problem as soon as some host is removed from  the  network.   Its

number  (or  numbers, if it has several logical addresses) cannot

be left unused, or the size of the  translation  table  would  be

determined  not  by  the number of logical addresses currently in

use in the network, but rather by the number of logical addresses

that  have ever been in use in the network, a number which may be

much larger, and which in fact has  no  bound.   Yet  it  is  not




                              -20-


IEN-183                              Bolt Beranek and Newman Inc.
                                                    Eric C. Rosen



acceptable simply to reassign the same logical addresses as hosts

enter or leave the network.  We all  have  some  experience  with

moving  to  a  new  location, getting a new telephone number, and

finding ourselves  frequently  getting  calls  intended  for  the

person  who  previously  had that number.  Such calls may persist

for years, especially if the  number  previously  belonged  to  a

business.   Receiving  phone  calls  or mail intended for someone

else who happens to have the  same  name  as  we  do  is  also  a

familiar  occurrence.   We  would  expect  analogous  problems if

logical  addresses  are  reassigned  (at  least,  if   they   are

reassigned  without some very long waiting period), especially if

the logical address previously belonged to a large service  host.

When  a  user  tries  to address a host which is no longer on the

network, he should receive  some  indication  of  that  fact;  he

should  NOT  have his data mis-delivered to some other host which

has been assigned the same name.  Thus it is preferable to have a

logical  addressing  scheme  which does not depend on the logical

addresses forming a contiguous set of numbers.


        Whatever means of organizing the table is chosen, it  may

still be useful to maintain a smaller table for use as a "cache."

The  cache  would  contain  the  n  most  recently  used  logical

addresses (where n is some small number), together with a pointer

to the absolute location of that logical  address  entry  in  the




                              -21-


IEN-183                              Bolt Beranek and Newman Inc.
                                                    Eric C. Rosen



main  translation table.  When it is necessary to do translation,

the  cache  would  be  searched  before  the  main  table.    The

assumption  is  that  once  one  packet  for a particular logical

address is received from a source host, many  more  will  follow.

Thus  it  pays to optimize the search for that particular logical

address.  Choosing the optimum size for the cache, and the  means

of  searching  it  (linear  or  binary) are issues left for later

resolution.  These issues must be dealt with carefully,  however;

one would not want to find that searching the cache takes as long

or longer than searching the main table.  It is worth emphasizing

that the cache should contain a pointer into the main translation

table, rather than a copy  of  the  list  of  physical  addresses

associated  with  a  particular logical address.  For multi-homed

logical addresses, this is more efficient, since it involves less

copying.   Also,  if  there  are  variables  associated  with the

physical addresses, this enables unique copies of  the  variables

to  be  kept  in  the  main  table.   (Suppose, for example, that

packets are to be sent on a  round-robin  basis  to  the  several

physical   addresses   corresponding  to  a  multi-homed  logical

address.  This requires a variable to  be  associated  with  each

physical  address,  indicating  whether that physical address was

the last one to be sent data.  This variable must be kept in  the

main  table, not the cache, since one cannot rely on a particular

logical address always being present in the cache.)  This  means,



                              -22-


IEN-183                              Bolt Beranek and Newman Inc.
                                                    Eric C. Rosen



of  course,  that  the  cache  must be cleared whenever there are

insertions or deletions into the main translation table, but that

should  not  be  very  expensive  as  long as such insertions and

deletions are relatively rare.




4  Initializing the Translation Tables


        We turn now to the issue of  how  the  translation  table

entries  are  to  be  set  up  in the first place.  That is, what

procedure is to  be  used  for  establishing  that  a  particular

logical  address  is  to  map  to  a  particular  set of physical

addresses.  One possibility for the ARPANET,  of  course,  is  to

have all the mappings set up by the Network Control Center (NCC).

This is quite reasonable in certain cases.  If  some  user  wants

his computer to be addressable by some new logical address (i.e.,

by a logical address not previously in use), it  makes  sense  to

have  him  contact  the  NCC  directly.   If  the user has proper

authorization, the NCC can then take action to  set  up  the  new

entry  in  all the translation tables.  A similar procedure would

also be appropriate if some logical  address  is  to  be  totally

removed  from  the translation tables (i.e., that logical address

will no longer be in use in that network).  This procedure  would

also  be appropriate when a particular computer is moved from one

location to another, necessitating a change  in  its  logical-to-



                              -23-


IEN-183                              Bolt Beranek and Newman Inc.
                                                    Eric C. Rosen



physical  mapping,  or  if  the functionality of two computers is

combined into one, so that two logical addresses  which  formerly

mapped  to  distinct  physical  addresses  now  map  to  the same

physical address.  What all these cases have in  common  is  that

they  are  relatively infrequent (i.e., occurring on the order of

days, rather than on the order  of  minutes),  and  they  require

considerable    advance    planning.     The   first   of   these

characteristics ensures that NCC personnel will  not  be  swamped

with   translation   table   changes.    The   second   of  these

characteristics makes it feasible to coordinate such  changes  in

advance  with  the NCC.  Unfortunately, not all translation table

changes  have  these  characteristics.   For  example,  we   have

suggested that a good logical addressing scheme should facilitate

port-sharing.  That is, some user might want to unplug one of his

computers  from  the  network  and  use  that  port  for  another

computer.  He should be able to  do  this  without  much  advance

planning,  and  without  having to explicitly coordinate with the

NCC.  As soon as the change is  made,  users  who  are  logically

addressing the first computer should be told that it is no longer

on the network; only the logical address of the  second  computer

should  map to this port.  If this change in the mapping does not

take place immediately, the result can be mis-delivery  of  data,

as  packets  which  are logically addressed to the first computer

get mis-delivered to the second.  A similar situation  arises  if



                              -24-


IEN-183                              Bolt Beranek and Newman Inc.
                                                    Eric C. Rosen



some  computer consists of several "logical hosts." Logical hosts

may come and go quite frequently, with  no  advance  planning  at

all.   The  logical  addressing  system  should  be able to adapt

immediately  to  such  changes,  without  any  need   for   human

intervention.   A related situation arises in the case of logical

addresses which  are  multi-homed.   We  have  already  discussed

various possible criteria for choosing among the several physical

addresses associated with a single multi-homed  logical  address.

But  before applying these criteria, any physical addresses which

are "inaccessible" from the source node  must  be  excluded.   If

some  host has two access lines into the network, and one of them

is inaccessible from a particular source node, then  all  traffic

from  that  source  node  should  be directed to the other access

line.  Indeed, this is one of  the  most  important  purposes  of

multi-homing.  This implies that a source node must have some way

of knowing that a  certain  physical  address  is  not  currently

accessible.   There  are  basically  two classes of reasons why a

given physical address might be inaccessible from a source  node.

The  first  is  that there is no path from the source node to the

destination node (either because the network is  partitioned,  or

because  the  destination  node  is  down).   This information is

readily available from the routing tables, and need not  be  kept

in  the  translation  tables.   It  is simple enough to check the

routing  tables  when  choosing  one  from  a  set  of   physical



                              -25-


IEN-183                              Bolt Beranek and Newman Inc.
                                                    Eric C. Rosen



addresses.   The  other  reason  why  a physical address might be

inaccessible is that the port itself, or the access line from the

port  to  the  host,  has  failed.   Functionally,  this  is  the

equivalent of unplugging the host from the port.  It  may  happen

quite   frequently,   however,  and  certainly  with  no  advance

planning.  As  long  as  the  node  itself  is  up,  the  routing

algorithm  will give no indication that the port is inaccessible;

this information must somehow get into  the  translation  tables.

Clearly, we do not want to depend on human intervention to ensure

that this sort of change gets made  in  the  translation  tables.

What  is  needed  here  is  a  quick and reliable means of making

changes  in  the  translation  tables,  not  the  cumbersome  and

unreliable method of contacting the NCC.  The same problem arises

when the inaccessible port becomes accessible again.   One  wants

to  be  able  to begin using this port again as soon as possible,

without having to wait until NCC personnel have time to make  the

appropriate  changes  in  the  translation  tables.   So although

certain sorts of changes to the translation tables can be made by

the   NCC,   many  sorts  of  changes  will  occur  suddenly  and

unexpectedly, and need to become effective immediately.   So  the

procedure of having all translation table changes made by the NCC

is not satisfactory.


        There is another sort of problem with having  translation




                              -26-


IEN-183                              Bolt Beranek and Newman Inc.
                                                    Eric C. Rosen



table changes made by the NCC.  The problem is that carelessness,

either by the NCC or by host site personnel, can result  in  mis-

delivery  of  data  if changes are made by the NCC.  Suppose, for

example, that a network controller makes a  typographical  error,

associating a logical address with an incorrect physical address.

If there is no further check on the validity of that mapping, one

computer  may  receive data intended for another.  A good logical

addressing  scheme   should   prevent   this   sort   of   simple

typographical  error  from  resulting  in mis-delivery.  The same

situation can occur if one computer is  carelessly  plugged  into

the  wrong  port.  In this case, networks which use only physical

addressing might also mis-deliver data.  However,  with  physical

addressing,  one  must  expect  mis-delivery  if some computer is

plugged into the wrong  port  (i.e.,  given  the  wrong  physical

address)  due  to carelessness.  With logical addressing, this is

not inevitable, and a good scheme should give  better  protection

against carelessness.


        Another possibility for setting up the translation  table

entries is to have each host, as it comes up on the network, tell

the network which logical addresses it wants to be  addressed  by

over   each   of   its  (physical)  ports.   This  would  require

augmentation of the host access protocol to  include  a  "Logical

Address  Declaration"  (LAD)  message.  A given host could put as




                              -27-


IEN-183                              Bolt Beranek and Newman Inc.
                                                    Eric C. Rosen



many logical addresses as it wanted in each LAD message.   Multi-

homed  hosts  would  send the same LAD message over each of their

ports.  The  logical  addresses  specified  in  the  LAD  message

received over a given port would all be mapped to that particular

physical address.  Hosts would be allowed to change their logical

addresses  at  any  time by sending a LAD message to the network.

Since a host may wish to add  or  delete  logical  addresses  for

itself  at  any  time, there would have to be two options for the

LAD message -- "add" and "delete."  Whenever  a  particular  port

goes  down  (either  because  the  port  itself fails to function

properly, or because the access line between the network and  the

host  fails, or because the host itself crashes), all mappings of

logical addresses to that port would be cancelled.  When the host

can once again communicate with the network through that port, it

would have to redeclare its logical addresses with a LAD  message

before it could receive any logically addressed traffic.


        Allowing each host to set up its own  logical-to-physical

address  mappings  in  this  manner  has  several advantages over

having all the mappings set up by the NCC.  This procedure allows

sudden  and unplanned mapping changes to take effect immediately,

with no need for advance planning and coordination with the  NCC.

Since  the  mappings  are  cancelled immediately when a port goes

down, this procedure helps to ensure that, if  one  of  a  multi-




                              -28-


IEN-183                              Bolt Beranek and Newman Inc.
                                                    Eric C. Rosen



homed host's ports is down, all data which is logically addressed

to that host will  go  to  the  other  ports.   If  one  host  is

unplugged  from  a  given port, and another plugged in its place,

the procedure ensures that the mapping  for  the  first  host  is

cancelled,   while  the  mapping  for  the  second  host  becomes

effective.  When a host goes down, there is  no  assumption  that

the   same   host  will  return  in  the  same  location.   Hence

carelessness on the part  of  site  personnel  or  NCC  personnel

cannot  result  in  mis-delivery of data; data which is logically

addressed to a certain host could only be  delivered  to  a  host

which has declared itself to have that logical address.


        There are, however, two quite serious problems with  this

procedure.  The first problem is that of spoofing.  That is, this

procedure offers no protection against the  situation  where  one

host declares itself to be addressable by a logical address which

is supposed to be the logical address of a different host.   Thus

the  procedure  allows  one  host to "steal" traffic intended for

another, simply by declaring itself  to  have  the  same  logical

address  as  the other.  This sort of spoofing might be done by a

malicious user, who is really  trying  to  steal  someone  else's

data,  or it might happen accidentally, as a result of programmer

or operator error.  In either case, we would like  to  have  some

procedure  which  is  less  prone to spoofing.  The other serious




                              -29-


IEN-183                              Bolt Beranek and Newman Inc.
                                                    Eric C. Rosen



problem with this procedure is  that  it  can  easily  cause  the

translation  tables  to  overflow  in  size.   If  every host can

specify an uncontrolled and unlimited number of logical addresses

for  itself,  there  is  no  bound on the size of the translation

tables.  Since only a finite amount of memory will  be  available

for the translation tables, it is clearly not acceptable to allow

each host to specify an arbitray number of logical addresses  for

itself.




5  Updating the Translation Tables


        We have examined two different procedures for setting  up

the  logical-to-physical  address  mappings,  and have found that

they both have problems.  Many of these problems can be resolved,

however,  by  a combination of the two procedures.  Let us define

two characteristics of  a  logical-to-physical  address  mapping,

which we will call "authorized" and "effective." A mapping from a

particular logical address to a particular  physical  address  is

"authorized"  if  a  host  which  connects to the network at that

physical  address  is  allowed  to  use  that  logical   address.

Authorizations  would  change  very  infrequently, and only after

considerable advance  planning.   Hence  it  is  appropriate  for

authorizations  to be determined (i.e., added and deleted) by the

NCC.  A mapping from a particular logical address to a particular



                              -30-


IEN-183                              Bolt Beranek and Newman Inc.
                                                    Eric C. Rosen



physical  address  would  be  said  to  be  "effective"  from the

perspective of a  given  source  node  if  (1)  that  mapping  is

authorized,  (2)  that  physical  address is accessible from that

source node, and (3) the host at that physical  address  has,  by

means  of  a  LAD  message,  declared itself to have that logical

address.  When a port goes down, all mappings to it  will  become

ineffective,  until  they  are made effective again by means of a

LAD message.  Logically addressed traffic will not  be  delivered

to  a particular physical address unless the mapping between that

logical address and that physical address is effective.   Changes

in  the  effectiveness  of a mapping will occur automatically, in

real-time, with no need for intervention by NCC personnel.   This

facilitates  multi-homing,  since  if  there  are  two authorized

mappings of a logical address to a physical address, and only one

is  effective,  that  one  can  be  chosen all the time until the

second becomes effective also.  It facilitates sharing  of  ports

(either  by  physical  or  by logical hosts), since each host has

control over the effectiveness (though not the authorization)  of

the  mappings  that affect it.  Carelessness by NCC personnel can

cause the wrong mappings to become authorized, but it  is  rather

unlikely  that  an  incorrectly  authorized  mapping could become

effective --  that  would  require  carefully  planned  malicious

intent.   Therefore,  such carelessness might prevent delivery of

data to some host, but would  not  cause  mis-delivery  of  data.



                              -31-


IEN-183                              Bolt Beranek and Newman Inc.
                                                    Eric C. Rosen



Carelessness  by site personnel, such as plugging a host into the

wrong port, would not  cause  mis-delivery  of  data,  since  the

mapping  of  that  host's logical address to that particular port

would not be authorized.  The possibility of spoofing is  greatly

reduced; since host A cannot pretend to be host B unless it is at

a port which is already authorized for host B.  The size  of  the

translation  table  cannot  increase without bound, since that is

determined by the number of authorized mappings,  and  cannot  be

increased  by  LAD  messages.   This  means,  of course, that the

network access protocol must be further modified so that  it  can

provide   positive  and  negative  acknowledgments  for  the  LAD

messages.  For each logical address that  a  host  specifies  for

itself  in  a  LAD  message,  the  network  must  return either a

positive   or   a   negative   acknowledgment.    The    positive

acknowledgment  would indicate that the mapping is authorized and

has become effective.  The negative acknowledgment would indicate

that the mapping is not authorized.


        It must be emphasized that the suggested  procedures  are

not  intended  to provide security in any very strict sense.  For

networks in which security  is  a  very  important  issue  (e.g.,

AUTODIN  II), further study of these issues should be carried out

by security experts.


        It should also be emphasized that these  procedures  will



                              -32-


IEN-183                              Bolt Beranek and Newman Inc.
                                                    Eric C. Rosen



allow  the  logical  addressing  scheme  to  continue to function

normally even if the NCC facilities are down.   It  does  require

centralized  intervention  to  add  or delete authorizations, and

this could not be done if the NCC were down.  For a fixed set  of

authorized  mappings,  however,  no  centralized  intervention is

required to determine the effectiveness of  the  mappings.   That

is, the real-time functionality and responsiveness of the logical

addressing scheme does not  depend  in  any  way  on  the  proper

functioning of the NCC.


        We have argued that the authorization of a mapping should

be  determined  by  the  NCC,  and the effectiveness of a mapping

should be determined by  the  network  node  which  contains  the

physical  address  (port)  to  which  the  mapping  is  made,  in

cooperation with the host that is connected  to  that  port.   We

have  also  argued  that  a full translation table (i.e., a table

containing all the effective mappings) should be stored  at  each

network  node  (or  more  precisely,  at  each network node which

serves as an access point for a host which can be either a source

or  a  destination  of logically addressed traffic).  However, we

have not yet discussed the algorithm by which  the  effectiveness

or  ineffectiveness  of  a particular logical-to-physical address

mapping is communicated to all network nodes.   We  turn  now  to

this  issue.   We  will  discuss  two  very different methods for




                              -33-


IEN-183                              Bolt Beranek and Newman Inc.
                                                    Eric C. Rosen



building up the translation tables at all nodes.


        The first method is based upon an extension  of  the  SPF

routing algorithm, wherein each logical address is treated like a

stub node.  In this method,  each  node  is  initialized  with  a

partial translation table.  This table contains a list of all the

logical addresses which are  AUTHORIZED  to  map  TO  that  node,

(i.e.,  all  the  logical  addresses which correspond to ports at

that node).  Each of these logical addresses is associated with a

particular  port  or ports at that node.  At initialization time,

each of these logical addresses is treated just as  if  it  is  a

neighboring  node  which  is  down,  and the node sends an update

(similar to a routing update) to all other nodes, indicating that

all  authorized  mappings to itself are ineffective.  When a host

comes  up  over  a  particular  port,  it  declares  its  logical

address(es)  by means of one or more LAD messages.  The node then

checks its table of authorized mappings, and acknowledges to  the

host  (either  positively  or  negatively)  each  logical address

mentioned in the LAD message.   Whenever  a  logical  address  is

positively  acknowledged, it becomes effective, and the node must

broadcast an update to all other nodes declaring that mapping  to

be  effective.  Whenever a host declares (via a LAD message) that

it no longer wants to be  addressable  by  a  particular  logical

address, an update must be generated declaring that mapping to be




                              -34-


IEN-183                              Bolt Beranek and Newman Inc.
                                                    Eric C. Rosen



ineffective.  Whenever a port goes down,  all  logical  addresses

mapping  to  it become ineffective, and an update indicating this

must be broadcast.  If the protocol  used  to  disseminate  these

updates  is  the  same  as  the  protocol  used in the ARPANET to

disseminate the updates of the SPF routing  algorithm,  then  all

nodes  will  be  able to build dynamically an up-to-date table of

effective mappings, just as the routing updates  enable  them  to

build an up-to-date topology table.  (The procedure used to build

the topology tables is described in [1].  The  updating  protocol

is  described  in [2] and [3].) In effect, this procedure extends

the routing algorithm to treat the hosts (or more precisely,  the

mappings  of  logical  addresses  to  physical addresses) as stub

nodes, and the ports as lines, except  that  there  is  no  delay

associated with a port, but only an up/down status.


        This procedure is attractive from a conceptual  point  of

view,  but it is not really cost-effective.  That is, it seems to

be too expensive to be practical.  One reason is that it is  hard

to  place  a  bound  on  the  size  of the updates.  The updating

protocol of the ARPANET routing  algorithm  is  quite  efficient,

because  the  updates  are  so small.  The maximum update size is

only 216 bits (from  a  node  with  5  neighbors).   The  logical

addressing  updates might be much longer, since there is no limit

on the number of logical addresses that may map to a given  node.




                              -35-


IEN-183                              Bolt Beranek and Newman Inc.
                                                    Eric C. Rosen



The  updates  would  also have to be sent periodically, even when

there in no change in state.  These  features  are  necessary  to

ensure reliability in the face of such events as partitions, node

crashes, updates received out of order, etc.  With no restriction

on  the number of logical addresses which can map to a given node

(and it seems unwise to build in such a restriction), there is no

restriction  on  update size, and hence no bound on the bandwidth

needed for updating, or on the extra delay which may  be  imposed

on data packets due to the need to transmit the updates.


        The updating protocol which  was  designed  for  the  SPF

routing  algorithm  was  designed to get the updates to all nodes

very quickly, and with 100% reliability,  even  in  the  face  of

various  types  of  network  failures.   This  extreme  speed and

reliability is necessary for routing  updates,  since  rapid  and

reliable  updating  of  the routing tables is necessary to ensure

the integrity of the network.  Routing failures, after  all,  can

make  the  network completely unusable, and can be very difficult

to recover from, since most recovery  techniques  depend  on  the

NCC's  ability  to  communicate  with  the  nodes,  which in turn

depends  upon   the   integrity   of   the   routing   algorithm.

Fortunately,  the  protocol  used  for  disseminating the logical

addressing updates does not need all  the  functionality  of  the

updating  protocol  used  for routing, since the integrity of the




                              -36-


IEN-183                              Bolt Beranek and Newman Inc.
                                                    Eric C. Rosen



logical addressing  scheme  is  not  quite  as  critical  as  the

integrity  of  the  routing  algorithm.  This enables us to use a

simpler and less expensive method of maintaining the  translation

tables, which we will now discuss.


        In this second method, each node is  initialized  with  a

translation  table  containing ALL the authorized mappings.  This

table would have an entry for every logical address that  can  be

used in the network.  Each logical address would be associated in

the table with all the physical addresses  to  which  it  has  an

authorized  mapping.   Associated  with  each  of  these physical

addresses would be a Boolean  variable  indicating  whether  that

particular  logical-to-physical  address  mapping is effective or

ineffective.  At  initialization  time  a  node  would  mark  all

mappings  to  itself  as  INEFFECTIVE,  and all mappings to other

nodes as EFFECTIVE.  Whenever a host declares itself, via  a  LAD

message, to have a certain logical address, the node looks in the

translation table to see if that mapping is authorized.  (This is

just an ordinary table look-up, indexed off the logical address.)

If not, a negative acknowledgment is sent to the  host.   If  the

mapping  is  authorized,  a positive acknowledgement is sent, and

the entry in the translation table is marked EFFECTIVE.  Whenever

a  port  goes  down,  the node marks all mappings to that port as

INEFFECTIVE.  Of course, this also requires a "reverse" search of




                              -37-


IEN-183                              Bolt Beranek and Newman Inc.
                                                    Eric C. Rosen



the  table  (i.e.,  a  search  based  on  a physical, rather than

logical address).  To make this more efficient, when the  initial

reverse  search is done at initialization time, the node can save

a list of pointers into  the  translation  table.   Each  pointer

would correspond to a physical address entry for that node.  If a

separate table of pointers is kept for each port, the  node  will

be able to find in a very efficient manner entries which map to a

particular port.  Using this methodology, each node's translation

table  will correctly indicate, for each of the logical addresses

that map to IT, whether or not that mapping  is  effective.   (Of

course,  these  pointers would have to be adjusted whenever table

insertions or deletions are made.)


        When a source host sends a logically  addressed  datagram

packet  into  the  network,  the  source  node  will  search  the

translation table for  the  correct  mapping.   If  that  logical

address  cannot  be  found,  i.e.,  its use is not authorized, an

error message indicating this fact  should  be  returned  to  the

host,  and  the  packet  discarded.   If  that logical address is

found, but all the corresponding physical  addresses  are  either

marked  INEFFECTIVE,  or  else  are unreachable (according to the

routing algorithm), then the packet should be discarded, and  the

host  informed  of  that fact.  If some of the physical addresses

are both reachable (according to routing) and  marked  EFFECTIVE,




                              -38-


IEN-183                              Bolt Beranek and Newman Inc.
                                                    Eric C. Rosen



then  one  should  be  chosen,  according to some set of criteria

(perhaps one of those which  we  discussed  above).   The  chosen

physical  address  should  be  placed in the packet header, along

with the logical address.  The packet should then be forwarded to

its  destination; in doing the forwarding, tandem nodes will look

only  at  the  physical  address.   According  to  the  procedure

described in the previous paragraph, all mappings to REMOTE ports

will be initially marked EFFECTIVE.  To see how such mappings can

get marked INEFFECTIVE, we must see what happens when a logically

addressed packet reaches its destination node.


        When a logically addressed datagram  packet  reaches  its

destination  node,  the node looks up that logical address in its

translation table.  It is possible, of course, that that  logical

address  will  not be found at all, or that it will be found, but

that there will be  no  authorized  mapping  to  this  particular

destination  node.  This would indicate some sort of disagreement

between the translation tables  at  the  source  and  destination

nodes.   There  are  three  possible causes of this disagreement:

(1) NCC error in setting up the translation tables, (2)  deletion

of  the  authorization  for that particular logical address while

the packet was in transit, or (3) a  race  condition,  whereby  a

translation  table  update authorizing the new logical address is

taking place, but the update has  not  reached  that  destination




                              -39-


IEN-183                              Bolt Beranek and Newman Inc.
                                                    Eric C. Rosen



node  yet.   In  any  case,  the  data packet should be discarded

without delivery, and an error message should be sent to the  NCC

indicating  receipt  of  a  packet  with  an unauthorized logical

address.  This will alert NCC personnel to a possible error.   If

the  authorization for that logical address was deleted while the

packet was in transit, however, then the NCC need  not  take  any

action;  having the destination node simply discard the packet is

the correct procedure.  If, on the other hand,  that  logical-to-

physical  mapping is really authorized, but the update making the

authorization has not yet reached the destination node,  then  we

want  to  take  the  same  action  as  we would take for a packet

delivered according to an  authorized  but  ineffective  mapping.

This action shall be described in the next paragraph.


        Suppose that, upon looking up the logical address in  the

translation  table,  the destination node does find an authorized

mapping to itself, but that mapping is marked ineffective.   Then

there  are  two  actions  to take.  The first action is to try to

re-address and then re-send the message.   Of  course,  this  can

only  be  done if the destination logical address is multi-homed,

and at least one  of  the  corresponding  physical  addresses  is

effective.   If  this  is  not  the  case,  the  packet  must  be

discarded.  The second action is to send a special  message  back

to  the  source  node of that datagram packet.  We will call this




                              -40-


IEN-183                              Bolt Beranek and Newman Inc.
                                                    Eric C. Rosen



message a "DNA message" (for "Destination Not Accessible").   The

DNA  message will specify that the particular logical-to-physical

address mapping used for that packet is not an EFFECTIVE mapping.

The  DNA  message  should  also  be sent in response to datagrams

which  appear  to  have  unauthorized  mappings   (see   previous

paragraph).   For  reliability, each logically addressed datagram

must carry the physical address of its source node (though not of

its  source  host),  so  that  the  DNA message can be physically

addressed to the source node.  It is not enough  for  the  packet

simply  to  carry the logical address of its source host, for two

reasons.  The first reason is that if the source host  is  multi-

homed,  the  destination node will not know which source node the

packet came from, and hence will not know where to send  the  DNA

message.   The  second  reason  has  to do with the fact that one

situation in which DNA messages  may  have  to  be  sent  is  the

situation  in which the translation table at the destination node

has been set up erroneously.  In this case, we  do  not  want  to

have  to rely on the integrity of the translation table to ensure

proper delivery of the DNA message.


        When a source node receives a DNA message indicating that

a  certain logical-to-physical address mapping is ineffective, it

must find the proper entry in its  translation  table,  and  mark

that  mapping  as ineffective.  Henceforth, incoming packets with




                              -41-


IEN-183                              Bolt Beranek and Newman Inc.
                                                    Eric C. Rosen



that  particular  logical  address  will  not  be  sent  to  that

particular  physical  address.   If the logical address is multi-

homed, packets will be sent to one or more of the other  physical

addresses,  unless  all the mappings for that logical address are

ineffective.  If this is  the  case,  packets  for  that  logical

address  will  be discarded by the source node, which should also

return some sort of negative acknowledgment to the  source  host.

We  see  then  that the DNA messages provide a feedback mechanism

which enables a source node to tell when a mapping  to  a  remote

port  is ineffective.  The source node has no way to tell whether

this is the case, until it sends a packet to  that  port.   After

sending the packet, it will be explicitly told by the DNA message

if the mapping is ineffective.  If it receives no DNA message, it

assumes that the mapping is effective.  This may mean, of course,

that some  logically  addressed  packets  are  sent  to  a  wrong

physical  address.  However, if there are other possible physical

addresses corresponding to that logical address, and the original

destination  node  has  one  of  those  other  mappings marked as

effective, the packet will be re-addressed and  re-delivered,  so

there  is no data loss.  Note that there are two possible reasons

why  a  given  logical-to-physical  address  mapping   might   be

ineffective:   (1) the physical port might not be operational, or

(2) the host at that physical address  might  not  have  declared

itself  addressable  with  that logical address.  If desired, the



                              -42-


IEN-183                              Bolt Beranek and Newman Inc.
                                                    Eric C. Rosen



DNA message can indicate which of these two reasons is applicable

in  the  particular case in hand.  This information can be stored

in the source node's translation table, and passed on  to  source

hosts  which  try  to  use  a  logical  address for which all the

mappings are ineffective.


        This procedure enables all  nodes  to  find  out  when  a

particular  authorized  mapping  is  ineffective.  We also need a

procedure to enable the nodes to find  out  when  an  ineffective

mapping becomes effective again (i.e., a port comes back up, or a

new LAD message is received at some remote site).  A  simple  but

effective  method  is the following.  At periodic intervals (say,

every 5 or 10 minutes) each node will go through its  translation

table  and  mark  ALL the entries which map to REMOTE ports to be

effective.  (Entries which map to  local  ports  will  be  marked

effective   or   ineffective   according  to  procedures  already

discussed.   The  current  procedure  will  not  apply  to   such

entries.)  This  enables  mappings to be used again shortly after

they become effective.  Of course, this  scheme  will  result  in

some packets being sent to the wrong physical address.  When that

happens, however, a DNA message will be  elicited,  causing  that

mapping  to  be  marked  ineffective  again  in that source node.

Furthermore, this scheme does  not  cause  any  unnecessary  data

loss,  since  packets  sent to the wrong physical address will be




                              -43-


IEN-183                              Bolt Beranek and Newman Inc.
                                                    Eric C. Rosen



re-addressed and re-delivered, if possible.


        Although this method requires all nodes  to  periodically

mark  all  mappings to remote ports effective, it is important to

understand that it  does  not  require  any  time-synchronization

among  the  various  nodes.  Also, there is no reason why all the

mappings have to be marked  effective  at  the  same  time.   For

example,  if  the translation table contains 600 mappings, rather

than marking all of them effective every 10 minutes,  it  may  be

more efficient to mark one mapping effective each second, thereby

cycling through the table  every  ten  minutes  (though  if  this

method  is  used,  it must take account of table compressions and

expansions  which  may  occur  as  the  NCC   adds   or   deletes

authorizations).


        There is also an issue as to the exact methodology to  be

used  to  send  the  DNA  messages.  The simplest method is for a

destination node to send a DNA message to the source node of each

packet which arrives as the result of an ineffective mapping.  If

this method is used, there is no need to use a reliable transport

protocol in sending the DNA messages.  If, for some reason, a DNA

message fails to get through to the  source  node,  more  packets

will  arrive  at  the  wrong  destination  node, causing more DNA

messages to be sent, until one  of  them  finally  gets  through.

This method, however, might generate a virtually unbounded number



                              -44-


IEN-183                              Bolt Beranek and Newman Inc.
                                                    Eric C. Rosen



of DNA messages, particularly in pure datagram networks  with  no

flow  or  congestion  control.   This in turn might contribute to

network congestion.  In order  to  gain  better  control  of  the

throughput  due  to  DNA  messages,  one could implement a scheme

which ensures that only  one  DNA  per  ineffective  mapping  per

source  node  can  be  sent within a certain time interval.  This

scheme would have a significant cost  in  table  space,  however.

Also,  it  would require some sort of reliable transport protocol

(e.g., positive acknowledgments from  the  source  node  when  it

receives the DNA message) to protect against the case where a DNA

message is  lost  in  transit.   This  issue  would  have  to  be

carefully considered before any implementation is done.


        The procedure to follow with virtual circuit  traffic  is

very  similar.   In  the  ARPANET,  a  single  virtual circuit or

"connection"  is  individuated  by  the  source  and  destination

physical  addresses.   The  user  takes  no  part in setting up a

connection; whenever a user sends a packet to the  network  which

is not a datagram, the network checks to see if a connection from

the user's physical address to the destination  physical  address

that  he  specified  is  already  in existence.  If not, the IMPs

automatically run a protocol to set up such a  connection.   With

logical  addressing,  we  would  want to redefine the notion of a

connection so that connections are  individuated  by  source  and




                              -45-


IEN-183                              Bolt Beranek and Newman Inc.
                                                    Eric C. Rosen



destination   LOGICAL  address,  rather  than  physical  address.

However, translation would be done only at connection setup time.

Thereafter,  all  virtual  circuit  packets  received  by a given

source node with the same source logical address and  destination

logical  address  would  be  sent  on  the same connection.  If a

destination node  receives  a  connection  setup  message  for  a

logical  address whose mapping is ineffective, it will refuse the

connection, just as  it  would  refuse  a  setup  message  for  a

physical  connection  to  a  dead  port.   When  the  source node

receives the  refusal  message,  it  will  mark  that  particular

logical-to-physical  mapping  as ineffective.  If the destination

logical address is multi-homed, the source node  can  attempt  to

set  up  the  connection  again,  but  with  a different physical

destination address.  If a mapping becomes  ineffective  after  a

connection  has  already  been  set up, the destination node will

take action to reset the connection, also  informing  the  source

node that the mapping is now ineffective.


        Note that logically  addressed  virtual  circuit  packets

need  not  carry in their headers the logical addresses of either

the source or destination hosts, since that  information  can  be

stored  in  the  connections tables at the source and destination

nodes.  Of course, all  packets  sent  on  a  particular  logical

connection  will  go  to  the  same  physical  destination  port.




                              -46-


IEN-183                              Bolt Beranek and Newman Inc.
                                                    Eric C. Rosen



However, if the destination node  or  port  goes  down,  and  the

destination    host   is   multi-homed,   the   above   procedure

automatically ensures that a new connection will be opened to one

of  the  ports  which  is not down.  Since the ARPANET connection

protocol is transparent to the user, the  user  need  never  know

that this has happened.


        It is interesting to compare this procedure (based on DNA

messages)  with  the previously discussed procedures (based on an

updating protocol similar  to  that  used  for  the  SPF  routing

algorithm).   The  latter  procedure  would ensure that all nodes

always agree (except during some very short transient period)  on

precisely  which  mappings  are  effective  and  which  are  not.

Mappings would be marked effective  (or  ineffective)  almost  as

soon  as  they  become so.  There would be no need for the source

nodes to probe the destination nodes by sending data  packets  to

possibly  incorrect  physical  addresses.   The  procedure we are

recommending does not have these features.   In  the  recommended

procedure,   different   nodes'   translation  tables  would  not

necessarily be in agreement all the time as to which mappings are

or  are  not  effective,  and  probing  is necessary.  This is an

acceptable situation though, since  the  sort  of  universal  and

immediate  agreement  which  is  necessary  to  ensure the proper

functioning of a routing algorithm just is not needed  to  ensure




                              -47-


IEN-183                              Bolt Beranek and Newman Inc.
                                                    Eric C. Rosen



the   proper   functioning  of  the  logical  addressing  scheme.

However, THE  LACK  OF  UNIVERSAL  AGREEMENT  DOES  REQUIRE  THAT

TRANSLATION  BE  DONE  AT  SOURCE NODES RATHER THAN TANDEM NODES,

since the DNA-based procedure, while designed to keep the  tables

at  source  nodes  up-to-date, will not necessarily have the same

effect at tandem nodes.  (That is, DNA messages are sent  to  the

source nodes, NOT to tandem nodes.)


        There is  only  one  situation  in  which  re-translation

should  be  done  at  the  tandem  nodes.   Suppose  a  logically

addressed packet arrives at a tandem node, and that  node,  after

checking  its  routing  table, sees that the physical destination

address of that packet  is  unreachable.   If  the  packet  is  a

virtual  circuit  packet,  or  the tandem node does not implement

logical addressing (i.e., does not contain a translation  table),

the  packet  must  simply  be  discarded.  But if the packet is a

datagram, and the tandem node does have a translation  table,  it

should  re-translate  the  destination  logical  address, and re-

address  the  packet.   This  procedure  can  help   to   prevent

unnecessary  data  loss.   Note that this tandem node translation

would happen only rarely, and only  in  situations  in  which  it

could  not  serve  to  defeat the criteria according to which the

source node translation was done.


        It should be noted that, with the  recommended  procedure



                              -48-


IEN-183                              Bolt Beranek and Newman Inc.
                                                    Eric C. Rosen



(unlike  the  alternative),  the size of the translation table at

each node is a function only of  the  number  of  authorizations.

That is, only changes in the authorizations require insertions or

deletions to the table.  This justifies our previous  claim  that

insertions and deletions are relatively rare events.


        It should also  be  pointed  out  that  nothing  in  this

procedure  prevents a computer from being multi-homed to a single

node.




6  Operational and Implementation Considerations


        This procedure requires each network node to  maintain  a

full   table  of  authorized  mappings.   There  are  operational

advantages to requiring all nodes  to  have  precisely  the  same

translation  table;  this simplifies the process whereby one node

can be reloaded from another in case of failure, and reduces  the

amount  of  site-dependent information that must be maintained in

the nodes.  (In  general,  the  more  site-dependent  information

there  is,  the  larger the Mean Time to Repair will be.) We have

not spoken explicitly of the way in which NCC  personnel  add  or

delete  authorizations.   This will require some protocol between

the nodes and the NCC.  This protocol would be  similar  in  some

ways  to  the  protocol  used  to  broadcast  software patches or




                              -49-


IEN-183                              Bolt Beranek and Newman Inc.
                                                    Eric C. Rosen



packages to the nodes.  However, since we want to be able to make

incremental  changes  to  the tables (rather than broadcasting an

entire new table each time a change must be made), the node  will

have  to  contain  routines  to add to or delete from the tables.

The node may have  to  inhibit  interrupts  while  modifying  its

table,  so  that no translations are done while the table is in a

state of flux.  Also, no reloads may be done from  a  node  whose

table  is  in  a  state of flux.  These last two restrictions are

needed to prevent race conditions; these restrictions are  easily

implemented.


        When  the  NCC  makes  a   change   to   the   table   of

authorizations,  it  will  want  to receive some sort of positive

feedback, indicating that the change has indeed been  made.   One

method of doing this is to associate a sequence number with every

"add" or "delete" command.  Each node could  periodically  report

to  the NCC the sequence number of the last command that it fully

executed, and an entry could  appear  in  the  log  whenever  the

sequence  number  is other than expected.  If the nodes refuse to

execute commands which are received out of sequence,  this  would

enable  the  NCC  to determine whether each node has received the

correct sequence of commands.


        If memory considerations make it impossible for each node

to  contain a table of ALL authorized mappings, it is possible to



                              -50-


IEN-183                              Bolt Beranek and Newman Inc.
                                                    Eric C. Rosen



get by with a shorter  table.   Strictly  speaking,  each  node's

table  need  contain only the logical addresses which map to that

node itself, PLUS those logical addresses which  the  node's  own

local  hosts  are  allowed  to use.  While this smaller table may

take less memory, it would,  however,  increase  the  operational

difficulties of table maintenance.  We have not yet said anything

explicit about the format of a logical address.  We recommend use

of  a 16-bit field for coding the logical addresses.  This should

be enough to prevent  bit-coding  limitations  from  placing  any

restriction on network growth.  The only other information needed

in the translation table is (1) destination node physical address

(8    bits    should    suffice),    (2)    one   bit   for   the

effective/ineffective variable, (3) enough bits to code the  port

numbers,  and  (4)  enough  bits  to code any variables needed to

implement the selection  criteria  used  for  multi-homed  hosts.

This  should  not  take  more  than two or three 16-bit words per

entry.  If space is a problem, it  is  possible  to  shorten  the

tables somewhat by deleting the port numbers.  Strictly speaking,

port numbers are only needed by the destination nodes, and  hence

need  not  appear  in  each node's copy of the translation table.

However, eliminating the  port  numbers  from  the  common  table

increases  the amount of site-specific information in the tables,

which is a disadvantage in itself.





                              -51-


IEN-183                              Bolt Beranek and Newman Inc.
                                                    Eric C. Rosen



        It goes without saying that the use of logical addressing

has  implications  for  the  network  access  protocol.   We have

already discussed one aspect  of  the  network  access  protocol,

viz.,  the  need  for the host to send LAD messages to the source

node, and the need for positive and negative  acknowledgments  to

be  returned  to  the host.  A LAD message from a particular port

contains a list of logical addresses, with an indication for each

one  as  to  whether  the  host wants the mapping of that logical

address to that port  to  be  effective  or  not.   When  a  host

declares a mapping to be ineffective, the source node must always

return a positive  acknowledgment,  and  must  mark  the  mapping

ineffective in its translation table.  However, if the mapping is

not authorized (i.e., not in the translation table),  the  source

node  should also return a warning to the source host, since host

error is likely.  When a host declares a mapping to be effective,

the   node   will   return   either   a   positive   or  negative

acknowledgment, depending upon whether the mapping is  authorized

or  not.   When  a  host  declares  an  authorized  mapping to be

effective, the node must mark it so.  The host should be  allowed

to  send  LAD  messages  to the node at any time, and they should

take effect immediately.









                              -52-


IEN-183                              Bolt Beranek and Newman Inc.
                                                    Eric C. Rosen



7  Network Access Protocol Implications


        The  use  of  a  logical  addressing  scheme   also   has

implications  on  the part of the network access protocol that is

used for ordinary data transport.  When a source  host  passes  a

message  to  its  source  node,  the message leader must indicate

whether logical or physical addressing is desired  (assuming  the

network  allows  both).   If  logical  addressing is desired, the

destination logical address must be indicated.  The  source  node

must  be  able  to  discard  that  message  (with  an appropriate

negative acknowledgment) if there is  no  effective  mapping  for

that  logical  address.   The  source  host  must also be able to

indicate its own logical address, if it wants to make this  known

to the destination host.  (Since the source host may have several

logical addresses, it must explicitly choose one to be carried to

the  destination  host.)  Again,  the source node must be able to

negatively acknowledge  and  then  discard  the  message  if  the

mapping  from  that logical address to the source host's physical

address is not effective.  Alternatively, one may want to  return

this  sort  of negative acknowledgment only if the source logical

address mapping is unauthorized, and allow the message to be sent

if the mapping is authorized but ineffective.  If this is done, a

particular "logical host" may be allowed to send data, but not to

receive it.




                              -53-


IEN-183                              Bolt Beranek and Newman Inc.
                                                    Eric C. Rosen



        When a logically addressed message  is  passed  from  the

destination node to the destination host, the message header must

contain the destination logical address  (since  the  destination

host  may  have  more  than  one logical address), and the source

logical address, if any.   This  implies,  of  course,  that  the

source and destination logical addresses of datagram packets must

be carried across the network in the packet header.  (For virtual

circuit  packets,  the  logical  addresses  can  be  kept  in the

connection blocks in  the  source  and  destination  nodes.)  The

internal  packet  header must also carry the physical destination

node number (for addressing at tandem nodes),  and  the  physical

source  node number (so that DNA messages can be returned without

having to rely on  the  integrity  of  the  translation  tables).

However,  these  physical  node numbers need not be passed to the

destination host.  Note that there is no need  for  the  internal

packet  header to carry source or destination port numbers, since

these are usually determined by the combination of physical  node

number  and  logical address.  In the case where a host is multi-

homed to a single node, the port numbers are not  so  determined,

but  the destination node can make a choice of ports "at the last

minute," either by choosing according  to  one  of  the  criteria

already  discussed,  or  by  choosing  the port with the shortest

queue.





                              -54-


IEN-183                              Bolt Beranek and Newman Inc.
                                                    Eric C. Rosen



[1]  E.C. Rosen, J.G. Herman, I. Richer, J.M. McQuillan, ARPANET
Routing Algorithm  Improvements  --  Third  Semiannual  Technical
Report, BBN Report No. 4088, April 1979, chapter 2.

[2]  J.M. McQuillan,  I.  Richer,  E.C.  Rosen,  D.P.  Bertsekas,
ARPANET  Routing  Algorithm  Improvements  --  Second  Semiannual
Report, BBN Report No. 3940, October 1978, chapter 4.

[3]  E.C. Rosen, "The Updating Protocol of ARPANET's New  Routing
Algorithm," Computer Networks, February 1980, Volume 4, p. 11.








































                              -55-